#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_map"

using namespace std;

/*HJJ QQ479287006
 *一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

 

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

int numDecodings(string s) {

    if (s.size() == 0 || (s.size() == 1 && s[0] == '0')) return 0;
    if (s.size() == 1) return 1;
    vector<int> dp(s.size() + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < s.size(); ++i) {
        dp[i + 1] = ((s[i] == '0') ? 0 : dp[i]);
        if (i > 0 && (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))) {
            dp[i + 1] += dp[i - 1];
        }
    }
    return dp.back();
}

//如果 只有 i这一种 那么 f(i)=f(i-1) ;//有前一个那么多
//如果 i 和前面的能组成一组 那么 f(i)=f(i-2)
// 成功的条件下 f(i)=f(i-1)+f(i-2)； 需要保证拿一个的时候 属于1-9 拿两个的时候 属于 10-26
//int numDecodings11(string s) {
//    if(s.size() == 0 || (s.size() == 1 && s[0] == '0')) return 0;
//    if(s.size() == 1) return 1;
//    vector<int> dp(s.size() + 1, 0);
//    //问题来了 这个怎么初始化好
//    dp[0] = 1;
//    for(int i = 1; i < s.size(); ++i){
//        int temp= 0;
//        if (i-2>=0)
//            temp=stoi(s.substr(i-2,2));
//        if (dp[i]>'0'&&dp[i]<'9'&& temp>=10 &&temp<27&&(i-2)>=0 ){
//            dp[i]=dp[i-1]+dp[i-2];
//        }else if (dp[i]>'0'&&dp[i]<'9')
//        {
//            dp[i]=dp[i-1];
//        }else if (temp>=10 &&temp<27&&(i-2)>=0 ) {
//            dp[i]=dp[i-2];
//        }
//
//
//    }
//    return dp.back();
//}

// dfs + 记忆化搜索
//int helper(string& s, map<int, int>& mp, int start){
//    if(mp.find(start) != mp.end()) { return mp[start]; }
//    if(start == s.size()) { mp[start] = 1; return 1; }
//    if(s[start] == '0') { mp[start] = 0; return 0; }
//    int res = helper(s, mp, start + 1);
//    if(start + 1 < s.size() && stoi(s.substr(start, 2)) <= 26)
//        res += helper(s, mp, start + 2);
//    mp[start] = res;
//    return res;
//}
//// dfs
//int helper(string& s, int start){
//    if(start == s.size()) { return 1; }
//    if(s[start] == '0') return 0;
//
//    int res = helper(s, start + 1);
//    if(start + 1 < s.size() && stoi(s.substr(start, 2)) <= 26)
//        res += helper(s, start + 2);
//    return res;
//}







unordered_map<int, int> mp;

//回溯写一下 返回最终的长度
int helper(string &s, int start) {

//    if (mp.find(start)!=mp.end())
//        return mp[start];
    //出口1 如果为0
    if (s[start] == '0')
        return 0;

    int aaaa = s[start];
    //我擦这边为啥不是 s.size()-1 不能减一 个别会不对 只有那些小于等于二的会差1
    if (s.size() == start)
        return 1;

    int res = helper(s, start + 1);//寻找一步的长度

    if (start < s.size() - 1 && stoi(s.substr(start, 2)) > 9 && stoi(s.substr(start, 2)) < 27) {
        res += helper(s, start + 2);//寻找一步的长度
    }

    // mp[start]=res;

    return res;

}

int numDecodings1111(string s) {
    int a = helper(s, 0);
    std::cout << a;
    return a;
}